package chapter01;

import java.util.LinkedList;
import java.util.List;

public class LetterCombinations {
    //回溯 深度优先遍历
    char[][] letter={{},{},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
    List<String> list=new LinkedList<>();
    StringBuilder stringBuilder=new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if(digits.length()<1){
            return list;
        }
        dfs(stringBuilder,digits);
        return list;
    }

    public void dfs(StringBuilder stringBuilder,String digits){
        if(stringBuilder.length()==digits.length()){
            list.add(stringBuilder.toString());
            return;
        }
        int currentDigit=digits.charAt(stringBuilder.length())-'0';
        for(int i=0;i<letter[currentDigit].length;i++){
            stringBuilder.append(letter[currentDigit][i]);
            dfs(stringBuilder,digits);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
    }
}
